/*
 * @lc app=leetcode.cn id=169 lang=cpp
 *
 * [169] 多数元素
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;     // 多数元素的候选值
        int count = 0; 

        // 遍历原数组，更新相关变量
        for (int num : nums) {
            if (num == candidate) {
                count++;
            } else {
                count--;
                if (count < 0) {
                    candidate = num;
                    count = 1;
                }
            }
        }
        
        // 返回结果
        return candidate;
    }
};
// @lc code=end

